package arithmetic1.test;

/*
    动态规划解决双核处理器问题
 */
public class Work2 {
    public static void main(String[] args) {
        int length[]={3072,3072,7168,3072,1024};
        int minTime=minTime(5,length);
        System.out.println("最小时间为:"+minTime);
    }

    //动态规划算法求出最小时间,n为任务数，length数组为每个任务要处理的数据量
    public static int minTime(int n,int length[]){
        //定义一个times来保存每个任务执行的时间
        int T[]=new int[length.length];
        //得到总的时间
        int sumTime=0;
        for(int i=0;i<T.length;i++){
            T[i]=length[i]/1024;
            sumTime+=T[i];
        }
        //求出总时间的一半就相当于背包的大小
        int size=sumTime/2;
        //定义一个二维数组来保存每一种可能下的最小时间,行为n+1，列为size+1
        int t[][]=new int[n+1][size+1];
        //动态规划
        for(int i=1;i<size+1;i++){  //i遍历背包大小
            for(int j=1;j<n+1;j++){     //j遍历任务数量
                if(T[j-1]>i){    //当前大小大于背包大小
                    t[j][i]=t[j-1][i];  //不会装入背包
                }else {     //当前大小不大于背包大小
                    t[j][i]=Math.max(t[j-1][i],T[j-1]+t[j-1][i-T[j-1]]);
                }
            }
        }
        //返回最小时间
        return sumTime-t[n][size];
    }
}
